package priv.conceit.study.leetcode.simple.official;

import java.util.Objects;
import java.util.Stack;

/**
 * 编号938
 * 二叉搜索树的范围和
 * <a href="https://leetcode-cn.com/problems/range-sum-of-bst/"></a>
 * 给定二叉搜索树的根结点 root，返回 L 和 R（含）之间的所有结点的值的和。
 * 二叉搜索树保证具有唯一的值。
 *
 * 二叉搜索树特点
 * 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
 * 本体就是求出X >= L 且 X <= R 的节点的和
 *
 * 示例 1:
 * 输入: root = [10,5,15,3,7,null,18], L = 7, R = 15
 * 输出: 32
 * 示例 2:
 * 输入: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
 * 输出: 23
 *
 *
 * 归根结底
 * 当前节点为 null 时返回 0
 * 当前节点 X < L 时则返回右子树之和
 * 当前节点 X > R 时则返回左子树之和
 * 当前节点 X >= L 且 X <= R 时则返回：当前节点值 + 左子树之和 + 右子树之和
 *
 * 1-前序遍历
 * 前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。
 * 效率低o(n)
 * 使用栈 数据结构来实现
 *
 * 2-递归
 * 推荐使用
 * 就是不好理解
 *
 * @author Conceit
 * @since 1.0.0, 2019/7/18
 */
public class RangeSumOfBst {

	public static void main(String[] args) {

	}

	public int rangeSumBST(TreeNode root, int L, int R) {

		return 0;
	}

	/**
	 * 递归
	 * @param root
	 * @param l
	 * @param r
	 * @return
	 */
	public int recursion(TreeNode root, int l, int r){

		//四组计算规则
		//当前节点为null返回0
		if(root==null){
			return 0;
		}

		//当前节点 X < L 时则返回右子树之和
		if(root.val<l){
			return recursion(root.right,l,r);
		}
		//当前节点 X > R 时则返回左子树之和
		if(root.val>r){
			return recursion(root.left,l,r);
		}
		//当前节点 X >= L 且 X <= R 时则返回：当前节点值 + 左子树之和 + 右子树之和
		//该情况是全满足需要优先计算
		//存疑 该步骤可以最后返回
		//if(root.val>=l&&root.val<=r){
		//}
		return root.val+recursion(root.left,l,r)+recursion(root.right,l,r);
	}

	/**
	 * 前序遍历
	 * 这还是全部不为空的全部入栈
	 * 效率低
	 * 不建议使用
	 *
	 *
	 * @param root
	 * @param l
	 * @param r
	 * @return
	 */
	public int dlr(TreeNode root, int l, int r){
		if(!this.vaild(root,l,r)){
			return 0;
		}
		Stack<TreeNode> treeNodeStack=new Stack<>();
		treeNodeStack.push(root);
		int sum=0;
		while (!treeNodeStack.empty()){
			//出栈
			TreeNode curTreeNode=treeNodeStack.pop();

			if(curTreeNode.val >=l&&curTreeNode.val<=r){
				sum+=curTreeNode.val;
			}

			//只要不为空都入栈
			//5节点左右分别为3和7
			//否则会跳过该节点，节点7就无法纳入计算
			if(null!=curTreeNode.left){
				treeNodeStack.push(curTreeNode.left);
			}
			if(null!=curTreeNode.right){
				treeNodeStack.push(curTreeNode.right);
			}
		}
		return sum;
	}

	public boolean vaild(TreeNode root, int l, int r){
		if(Objects.isNull(root)){
			return Boolean.FALSE;
		}
		return Boolean.TRUE;
	}



	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}
}
